// Time:  O(logn)
// Space: O(1)

// g++ -o binary-search binary-search.cpp -std=c++11

#include <vector>
#include <iostream>

class Solution {
public:
    int search(std::vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while (left <= right) {
            auto mid = left + (right-left) / 2;
            if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }
};

int main() {
    Solution solution;
    std::vector<int> nums = {-1, 0, 3, 5, 9, 12};
    int target = 9;
    int result = solution.search(nums, target);
    std::cout << "Index of " << target << " is: " << result << std::endl;
    return 0;
}